package main.剑指OfferⅠ;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Day25 {
    public static void main(String[] args) {
        System.out.println("剑指Offer29.顺时针打印矩阵");
        System.out.println("剑指Offer31.栈的压入、弹出序列");
    }
}

class Offer29{
    List<Integer> list;
    public void process(int[][] matrix,int leftR,int leftC,int rightR,int rightC){
        if (leftR>rightR||leftC>rightC) return;
        if (leftR==rightR){//仅一行
            for (int i=leftC;i<=rightC;i++) list.add(matrix[leftR][i]);
            return;
        }else if (leftC==rightC){//仅一列
            for (int i=leftR;i<=rightR;i++) list.add(matrix[i][leftC]);
            return;
        }else {
            for (int i = leftC; i <= rightC; i++) list.add(matrix[leftR][i]);//上行
            for (int i = leftR + 1; i <= rightR; i++) list.add(matrix[i][rightC]);//右列
            for (int i = rightC - 1; i >= leftC; i--) list.add(matrix[rightR][i]);//下行
            for (int i = rightR - 1; i > leftR; i--) list.add(matrix[i][leftC]);//左列
            process(matrix, leftR + 1, leftC + 1, rightR - 1, rightC - 1);
        }
    }
    public int[] spiralOrder(int[][] matrix) {
        list=new ArrayList<>();
        int row= matrix.length,col=0;
        if (row!=0) col=matrix[0].length;
        if (row>0&&col>0) process(matrix, 0, 0, row - 1, col - 1);
        int[] result=new int[list.size()];
        for (int i=0;i<list.size();i++) result[i]=list.get(i);
        return result;
    }
}

class Offer31{
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int pop=0,push=0;
        Stack<Integer> stack=new Stack<>();
        while (pop<popped.length){
            while (push<pushed.length&&(stack.isEmpty()||(!stack.isEmpty()&&stack.peek()!=popped[pop]))) {//压入
                stack.push(pushed[push]);
                push++;
            }
            while (!stack.isEmpty()&&stack.peek()==popped[pop]){//弹出
                stack.pop();
                pop++;
            }
            if (push==pushed.length&&!stack.isEmpty()&&stack.peek()!=popped[pop]) return false;//不能正常弹出
        }
        return true;
    }
}